package pers.tz.题目.leetcode.树;

import pers.tz.common.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author irony
 * @date 2024-03-13
 */
public class leetcode_0958_二叉树的完全性检验 {
//给你一棵二叉树的根节点
// root ，请你判断这棵树是否是一棵 完全二叉树 。
//
// 在一棵 完全二叉树 中，除了最后一层外，所有层都被完全填满，并且最后一层中的所有节点都尽可能靠左。最后一层（第 h 层）中可以包含
// 1 到
// 2ʰ 个节点。
//
// 示例 1：
//输入：root = [1,2,3,4,5,6]
//输出：true
//解释：最后一层前的每一层都是满的（即，节点值为 {1} 和 {2,3} 的两层），且最后一层中的所有节点（{4,5,6}）尽可能靠左。
//
// 示例 2：
//输入：root = [1,2,3,4,5,null,7]
//输出：false
//解释：值为 7 的节点不满足条件「节点尽可能靠左」。
//
// 提示：
// 树中节点数目在范围 [1, 100] 内
// 1 <= Node.val <= 1000

    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        TreeNode t6 = new TreeNode(6);

        t1.left = t2;
        t1.right = t3;

        t2.left = t4;
        t2.right = t5;

        t3.left = t6;

        System.out.println(isCompleteBinaryTree(t1));
    }

    // 1. 有右孩子但没有左孩子
    // 2. 在非满节点之后（右边），出现了非叶子节点
    public static boolean isCompleteBinaryTree(TreeNode root) {
        if (root == null) {
            // 我这里视空树为非完全二叉树
            return false;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        // 是否遇到了非满节点
        boolean mustHaveNoChild = false;

        while (!queue.isEmpty()) {
            TreeNode head = queue.poll();

            // 如果有右孩子但没有左孩子
            if (head.right != null && head.left == null) {
                return false;
            }

            // 如果在非满节点之后出现了非叶子节点
            if (mustHaveNoChild && (head.left != null || head.right != null)) {
                return false;
            }

            // 标记非满节点
            if (head.left == null || head.right == null) {
                mustHaveNoChild = true;
            }

            // 广度优先遍历
            if (head.left != null) {
                queue.add(head.left);
            }
            if (head.right != null) {
                queue.add(head.right);
            }
        }
        return true;
    }
}
